High Speed Packet Switching Networks
Data transmission is now evolving with a specific focus on applications and by integrating a fundamental shift in the customer traffic profile. Driven by the growth of workstations, the local area networks interconnection, the distributed processing between workstations and super computers, the new applications and the integration of various and often conflicting structures—hierarchical versus peer to peer, wide versus local area networks, voice versus data—the data profile has become more bandwidth consuming, bursting, non-deterministic and requires more connectivity. Based on the above, there is strong requirement for supporting distributed computing applications across high speed networks that can carry local area network communications, voice, video and traffic among channel attached hosts, business, engineering workstations, terminals, and small to intermediate file servers. This vision of a high speed multi-protocol network is the driver for the emergence of fast packet switching networks architectures in which data, voice, and video information is digitally encoded, chopped into small packets and transmitted through a common set of nodes and links.
An efficient transport of mixed traffic streams on very high speed lines means for these new network architecture a set of requirements in term of performance and resource consumption which can be summarized as follows    a very high throughput and a very short packet processing time,    a very large flexibility to support a wide range of connectivity options,    an efficient flow and congestion control.
Throughput and Processing Time
One of the key requirement of high speed packet switching networks is to reduce the end to end delay in order to satisfy real-time delivery constraints and to achieve the necessary high nodal throughput for the transport of voice and video. Increases in link speeds have not been matched by proportionate increases in the processing speeds of communication nodes and the fundamental challenge for high speed networks is to minimize the processing time and to take full advantage of the high speed/low error rate technologies, most of the transport and control functions provided by the new high bandwidth network architectures are performed on an end to end basis. The flow control and particularly the path selection and bandwidth management processes are managed by the access points of the network which reduces both the awareness and the function of the intermediate nodes.
Connectivity
In high speed networks, the nodes must provide a total connectivity. This includes attachment of the user's devices, regardless of vendor or protocol, and the ability to have the end user communicated with any other device. The network must support any type of traffic including data, voice, video, fax, graphic or image. Nodes must be able to take advantage of all common carrier facilities and to be adaptable to a plurality of protocols. All needed conversions must be automatic and transparent to the end user.
Congestion and Flow Control
Communication networks have at their disposal limited resources to ensure an efficient packets transmission. An efficient bandwidth management is essential to take full advantage of a high speed network. While transmission costs per byte continue to drop year after year, transmission costs are likely to continue to represent the major expense of operating future telecommunication networks as the demand for bandwidth increases. Thus considerable efforts have been spent on designing flow and congestion control processes, bandwidth reservation mechanisms, routing algorithms to manage the network bandwidth. An ideal network should be able to transmit an useful traffic directly proportional to the traffic offered to the network and this as far as the maximum transmission capacity is reached. Beyond this limit, the network should operate at its maximum capacity whatever the demand is.
Routing Modes
A general problem in the communication networks is to find a path between a source and a destination node. When the network is using datagrams, the path selection must be done individually for each packet. For virtual circuits, the path decision is done once only at the time of the connection (or session) establishment. In both cases, the choice of a routing algorithm is not easy because it must satisfy a large number of often conflicting requirements. However, the routing algorithm must allow to exploit the network in an optimal way, according to a criterion which can vary with the utilization type. In most of the cases, the network is realized in a way to minimize the packet transit time and to transfer the maximum number of packets. In other cases, the objective is to decrease the communication cost, or to develop a reliable network able to operate correctly either in case of catastrophic line, node failure or peaks of traffic.
Because of the variety of the constraints, there are a large number of different routing types like flooding routing, random or stochastic routing, deterministic routing. This last routing technique can be implemented according to particular modes such as fixed or adaptive routing, centralized or distributed routing, node by node or end to end routing, connection oriented or connectionless routing . . . .
Adaptive Routing
Contrary to the Fixed Routing, where the routing rules are established once for all, the purpose of the Adaptive Routing is to satisfy at any time the optimization criteria. Tables are permanently updated according for example, the instantaneous state of the traffic on the links.
Distributed Routing
When the characteristics of the network fluctuate, it is possible to adapt the routing by assigning to one node the responsibility to update periodically the routing tables according to the traffic and the topology. The Distributed Routing is a method in which neighboring nodes are exchanging messages concerning the traffic and the network conditions to update their own routing table.
End-to-End Routing
The Adaptive and Distributed Routing are both currently used together in most high speed networks. In order to minimize the processing time and to take full advantage of the high speed/low error rate technologies, the transport and control functions provided by the high bandwidth networks are performed on an end to end basis. No hop by hop error recovery or retransmission is envisioned in high speed, high performance (low error) links and thus, there is no need for transit nodes to be aware of individual transport connections. The originating node is responsible for calculating the route that a packet must take through the network. The routing of the packets presents two aspects for which a wide range of implementing methods exists:    1. Determining what the route for a given connection shall be,    2. Actually switching the packet within a switching node.
Connection-Oriented Routing
One distinguishing characteristic of a network is the presence or absence of a “connection” between end users. They are many ways of constructing connectionless or connection-oriented networks. In most of cases, packets using different routing modes can share the same data transmission facilities. Most of the high speed connections are established on a reserved path to guarantee the bandwidth and the quality of service requested by the user. The path across the network is computed in response to each connection request by the originating node. The computed path is based on the parameters characterizing the network connection's requirements and on link capacity and load information maintained within each network node. The originating node sends a reservation request to the end node. As the bandwidth request packet flows along the chosen path, each transit node determines whether it has enough capacity to accept the new connection. If the connection is accepted, the requested bandwidth is reserved. Changes are reflected in every node of the network by means of control messages. Once a connection is established, there is no need to place a destination address in the packet header every time a packet is sent. All that is needed is an identifier to specify which connection is to be used for this packet. Due to the low packet overhead, the connection oriented routing technique is particularly adapted to the transmission of very short packets (for example real-time voice connections). This technique requires that connection tables be set up and maintained dynamically in each node and this restricting makes datagram transport quite inefficient. The implementation of flow and congestion control in a connection oriented network is easier than in a connectionless one because network nodes can regulate the flow on individual connections. However, when a link or a node becomes inoperative (goes down) connections that were passing through the affected link or node are typically lost. A new connection must be established through a different route. This takes time and may disrupt the connection at the end user level. The process for rerouting the connection without disrupting it at the end user level is called “Non-Disruptive Path Switch (NDPS)”.
Non-Disruptive Path Switch
NDPS Triggering
The Non-Disruptive Path Switch for a network connection with resource reservation is triggered by a number of situations including:    a link or a node along an existing the path fails,    a network management request could cause an NDPS as the result of an operator intervention, for example, to move a path back to an earlier, preferred path,    a resource reservation during a network connection set up failed, in which case NDPS is used to find another path with enough resources available,    a request for a connection bandwidth increase along an existing path fails, resulting in a NDPS for a new path with increased bandwidth,    a path end to end delay changes and becomes incompatible with the committed connection quality-of-service,    a preemption request for a path occurs.
The NDPS is also valid for network connections with no resource reservation, and then the first two of these reasons apply.
New Path Establishment
The NDPS procedure, applied at connection level, consists in taking down the existing path and performing a new path set up. These activities can be performed in parallel or in sequence:    If the existing path is inoperative, for example after a link failure, the path takedown and the new path set up activities will be performed in parallel.    If the existing path is still operational, for example after a failed bandwidth increase request, the existing path will still be used while the the new path is being be set up. When the new path is set up, the network connection is switched to the new path, and then the first path is taken down.
When a path is taken down, a request is sent to all the transit nodes handling the connection along the path to release the reserved network resources (in term of bandwidth, labels . . . ) associated with this specific connection. The path set up is very similar to the original network connection set up. The process is initiated by the origin node and consists in selecting a new path and requesting the transit nodes along this path to reserve network resources for this specific connection.
Path Selection
The role of the Path Selection process is to determine optimum paths for users across the network each time a connection is requested. This implies the allocation of network resources to users in order to guarantee their quality-of-service requirements while optimizing the overall throughput within the network. This function takes place entirely within the origin node. Various quality of service parameters may be specified by the users, some of them in order to satisfy real-time delivery constraints, others related to non real-time data traffic transfer . . . . The origin node computes a path to the destination node that is capable of carrying the new connection and providing the level of service required by the new connection. The Path Selection algorithm uses data describing the current traffic load in the entire network (nodes and links). Such data are stored in a topology database located in each node of the network. If no suitable path can be found to meet all requirements, the connection is rejected. Once, the origin node has found a suitable path, a set up message is generated which traverses the selected route, updating the resource allocations for each link visited by the set up message. To meet high throughput, paths are selected and resources reserved once only at the time of the connection establishment. The Path Selection algorithm takes into account various constraints which comes both from the user (quality-of-service requirements, user's traffic characteristics) and from the current network topology and bandwidth allocation. In addition, the algorithm maximizes the network throughput by choosing a path with the least number of hops and which tends to achieve an even distribution of the traffic among the links. Once an appropriate path has been selected, the network connection establishment process takes place, and only then are the resources along the path reserved.
Non-Disruptive Path Switch Delay
In case of link failure, it is important to reroute the traffic on alternate paths without any disruption of the end user connections. However, selecting a path and setting up a connection can take considerable processing overhead in network nodes and can generate a significant delay. For end nodes supporting multiple connections set up requests simultaneously, it is easy to have some sort of scheduling to avoid bottlenecks in the connection set up process. But nevertheless, the time for establishing a connection may be huge. For permanent connections the set up delay probably does not have very much meaning. However, for connections service in real-time, this is a very important parameter, especially since some connections terminate in equipment that runs time-outs.
In general, the closer to the destination node the link is, the more the link carries connections towards this destination node. A failure on a link adjacent to an origin or destination node may involves the rerouting of a lot of connections and may lead to a high number of simultaneous new path set up. The establishment in parallel of multiple new connections through alternate routes takes time and may disrupt the connections at the end user level. The Non-Disruptive Path Switch mechanism assumes that:    1. first, the physical network has enough residual capacity to accommodate the network connections affected by the failure event, and    2. second, the path switching delay must be minimum in order to preserve the connections at the end user level.
Therefore, a very fast path switching must be implemented to avoid traffic disruption in some critical cases (typically when a great amount of real-time connections need to be immediately rerouted).